package Tree;

public class item96 {
    public int numTrees(int n) {
        if(n==0||n==1) return n;
        int res =  build(1,n);
        return res;
    }

    private int build(int left, int right) {
        int res =0;
        if(left>right) return 1;
        for (int i = left; i <=right ; i++) {
            int lt = build(left, i - 1);
            int rt = build(i + 1, right);
            res = res+ lt*rt;
        }
        return res;
    }
}
